Computational thinking and Problem-solving

19.1 Algorithms

Candidates should be able to:

1. Show understanding of linear and binary searching methods

   Notes and guidance

2. Write an algorithm to implement a linear search
3. Write an algorithm to implement a binary search
4. The conditions necessary for the use of a binary search
5. How the performance of a binary search varies according to the number of data items :::
6. Show understanding of insertion sort and bubble sort methods

   Notes and guidance

7. Write an algorithm to implement an insertion sort
8. Write an algorithm to implement a bubble sort
9. Performance of a sorting routine may depend on the initial order of the data and the number of data items :::
10. Show understanding of and use Abstract Data Types (ADT)

    Notes and guidance

11. Write algorithms to find an item in each of the following: linked list, binary tree
12. Write algorithms to insert an item into each of the following: stack, queue, linked list, binary tree
13. Write algorithms to delete an item from each of the following: stack, queue, linked list
14. Show understanding that a graph is an example of an ADT. Describe the key features of a graph and justify its use for a given situation. Candidates will not be required to write code for a graph structure :::
15. Show how it is possible for ADTs to be implemented from another ADT

    Notes and guidance

    Describe the following ADTs and demonstrate how they can be implemented from appropriate built- in types or other ADTs: stack, queue, linked list, dictionary, binary tree

16. Show understanding that different algorithms which perform the same task can be compared by using criteria (e.g. time taken to complete the task and memory used)

    Notes and guidance

    Including use of Big O notation to specify time and space complexity

19.2 Recursion

Candidates should be able to:

1. Show understanding of recursion

   Notes and guidance

2. Essential features of recursion
3. How recursion is expressed in a programming language
4. Write and trace recursive algorithms
5. When the use of recursion is beneficial :::
6. Show awareness of what a compiler has to do to translate recursive programming code

   Notes and guidance

   Use of stacks and unwinding